package basic

import kotlin.random.Random

class Sorts {
    fun bubbleSort(nums: IntArray): IntArray {
        var exchanged = false
        for (i in nums.indices.reversed()) {
            for (j in 0 until i) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1)
                    exchanged = true
                }
            }
            if (!exchanged) {
                break
            }
        }
        return nums
    }

    fun insertionSort(nums: IntArray): IntArray {
        for (i in 1 until nums.size) {
            for (j in i downTo 1) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1)
                }
            }
        }
        return nums
    }

    fun shellSort(nums: IntArray): IntArray {
        var gap = 1
        while (gap <= nums.size / 3) {
            gap = gap * 3 + 1
        }
        while (gap > 0) {
            for (i in gap until nums.size) {
                for (j in i downTo gap step gap) {
                    if (nums[j] < nums[j - gap]) {
                        swap(nums, j, j - gap)
                    }
                }
            }
            gap = (gap - 1) / 3
        }
        return nums
    }

    fun mergeSort(nums: IntArray) {
        mergeSort(nums, 0, nums.size - 1)
    }

    fun quickSort(nums: IntArray) {
        partition(nums, 0, nums.size - 1)
    }

    private fun partition(nums: IntArray, left: Int, right: Int) {
        if (left >= right) return
        val pivot = nums[right]

        var littleBound = left
        var bigBound = right - 1

        while (littleBound < bigBound) {
            when {
                nums[littleBound] < pivot -> {
                    littleBound++
                }
                nums[bigBound] >= pivot -> {
                    bigBound--
                }
                else -> {
                    swap(nums, littleBound, bigBound)
                }
            }
        }
        val newPivotIndex = if (nums[littleBound] < pivot) {
            littleBound + 1
        } else {
            littleBound
        }
        swap(nums, newPivotIndex, right)
        partition(nums, left, newPivotIndex - 1)
        partition(nums, newPivotIndex + 1, right)
    }

    private fun mergeSort(nums: IntArray, left: Int, right: Int) {
        if (left == right) {
            return
        }
        val mid = left + (right - left) / 2
        mergeSort(nums, left, mid)
        mergeSort(nums, mid + 1, right)
        merge(nums, left, mid + 1, right)
    }

    private fun swap(nums: IntArray, i: Int, j: Int) {
        val temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    }

    private fun merge(nums: IntArray, leftPtr: Int, rightPtr: Int, rightBound: Int) {
        // [1,3,5,7,2,4,6,8]
        // [1,3,5,7,2,4,6]
        val mid = rightPtr - 1
        val temp = IntArray(rightBound - leftPtr + 1)

        var i = leftPtr
        var j = rightPtr
        var k = 0

        // [0,mid] [mid+1,size-1]
        while (i <= mid && j <= rightBound) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++]
            } else {
                temp[k++] = nums[j++]
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++]
        }
        while (j <= rightBound) {
            temp[k++] = nums[j++]
        }
        temp.copyInto(nums, leftPtr)
    }
}

fun generateList(size: Int): IntArray {
    val ret = IntArray(size)
    for (i in ret.indices) {
        ret[i] = Random.nextInt()
    }
    return ret
}

fun isSorted(list: IntArray): Boolean {
    for (i in 0 until list.size - 1) {
        if (list[i] > list[i + 1]) {
            return false
        }
    }
    return true
}

fun main() {
    val originList = generateList(100000)
    val sorts = Sorts()
    var copy: IntArray
    var startTime: Long
    var endTime: Long

    copy = originList.clone()
    startTime = System.currentTimeMillis()
    copy.sort()
    endTime = System.currentTimeMillis()
    println("default used time: ${endTime - startTime}ms. Is correct: ${isSorted(copy)}")

//    copy = originList.clone()
//    startTime = System.currentTimeMillis()
//    sorts.bubbleSort(copy)
//    endTime = System.currentTimeMillis()
//    println("bubble used time: ${endTime - startTime}ms. Is correct: ${isSorted(copy)}")

//    copy = originList.clone()
//    startTime = System.currentTimeMillis()
//    sorts.insertionSort(copy)
//    endTime = System.currentTimeMillis()
//    println("insertion used time: ${endTime - startTime}ms. Is correct: ${isSorted(copy)}")

//    copy = originList.clone()
//    startTime = System.currentTimeMillis()
//    sorts.shellSort(copy)
//    endTime = System.currentTimeMillis()
//    println("shell used time: ${endTime - startTime}ms. Is correct: ${isSorted(copy)}")

    copy = originList.clone()
    startTime = System.currentTimeMillis()
    sorts.quickSort(copy)
    endTime = System.currentTimeMillis()
    println("merge used time: ${endTime - startTime}ms. Is correct: ${isSorted(copy)}")

    copy = originList.clone()
    startTime = System.currentTimeMillis()
    sorts.mergeSort(copy)
    endTime = System.currentTimeMillis()
    println("quick used time: ${endTime - startTime}ms. Is correct: ${isSorted(copy)}")
}